package 代码记录.指定公司代码练习记录.华为_2024.分值200;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author zx
 * @create 2024-02-16 14:44
 * 搜索矩阵问题 - 类似于矩阵中的路径_12
 */
public class 找单词_11 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[][] arr = new char[n][n];
        for(int i = 0;i < n;i++){
            String in = sc.nextLine();
            String[] temp = in.split(",");
            for(int j = 0;j < n;j++) {
                char c = temp[j].charAt(0);
                arr[i][j] = c;
            }
        }
        String str = sc.next();
        boolean res = exist(arr, str);
        if(!res){
            System.out.println("N");
        }
    }
    public static boolean exist(char[][] arr, String str) {
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr[0].length; j++) {
                LinkedList<int[]> path = new LinkedList<>();
                if (dfs(arr, str, i ,j,0, path)) {
                    printPath(path);
                    return true;
                }
            }
        }
        return false;
    }
    private static boolean dfs(char[][] arr, String str, int i, int j, int k, LinkedList<int[]> path) {
        if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length) {
            return false;
        }
        if(arr[i][j] != str.charAt(k)){
            return false;
        }
        path.add(new int[] {i, j});
        if (path.size() == str.length()) {
            return true;
        }
        if(k == str.length() - 1) {
            return true;
        }
        arr[i][j] = ' ';
        boolean res = dfs(arr, str, i + 1, j, k + 1, path) ||
                dfs(arr, str, i - 1, j, k + 1, path) ||
                dfs(arr, str, i, j + 1, k + 1, path) ||
                dfs(arr, str, i , j - 1, k + 1, path);

        arr[i][j] = str.charAt(k);
        if (!res) {
            path.removeLast();
        }
        return res;
    }
    private static void printPath(LinkedList<int[]> path) {
        StringBuilder res = new StringBuilder();
        for (int[] pos : path) {
            res.append(pos[0]).append(",").append(pos[1]).append(",");
        }
        System.out.println(res.substring(0, res.length() - 1));
    }
}
